This invention relates to an apparatus for decimal multiplication for taking the sum of a partial product and an intermediate product by a loop adder and more particularly to an apparatus for decimal multiplication which enables high speed loop addition by using a carry save adder as the loop adder or carry save adders. This application is related with applications, U.S. Ser. No. 462,423 filed on Jan. 31, 1983, now U.S. Pat. No. 4,603,397 and U.S. Ser. No. 549,809 filed on Nov. 8, 1983, now U.S. Pat. No. 4,635,220.
When it is intended to multiply a multiplicand in binary code decimal form by a multiplier also in binary coded decimal form to obtain a final product in binary coded decimal form, as shown in FIG. 1, there is commonly used a system for effecting multiplications of a multiplicand by a multiplier having a predetermined processing width (for example, 1 digit) to provide n partial products, and this system then produces the final product by the addition of these partial products 1-n.
One example of the conventional apparatus for decimal multiplication for carrying out the operation such as shown in FIG. 1 is shown in FIG. 2. In this figure, the multiplication of a multiplier set in a multiplier register 1 and a multiplicand set in a multiplicand register 2 is carried out as follows. When a decimal partial product generator 4 is activated, a first decimal partial product operation of the multiplicand set in the multiplicand register 2 and the predetermined processing width partitioned out from the lower order digit of the multiplier set in the multiplier register 1 is performed, and this first decimal partial product is set in a partial product register 6. At the same time, zero (0) is set in an intermediate product register 5 (as an initial value), and the multiplier set in the multiplier register 1 is right-shifted by the partitioned-out data width by a shifter 3 and set again in the multiplier register 1. Next, the initial value 0 set in the intermediate product register 5 and the first decimal partial product set in the partial register 6 are added in a decimal loop adder 7 and the first decimal intermediate product is transferred to and set in the intermediate product register 5. Practically, the output from the decimal loop adder 7 is right-shifted by the predetermined processing width of the multiplier and set in the intermediate product register 5. The lowest order of the output from the decimal loop adder 7 corresponding to the predetermined processing width of the multiplier, is transferred to and set in the highest order multiplier predetermined processing width position of the multiplier register 1 through line 99, as the lowest order of the final product. A similar operation is repeated for all of the significant digits of the multiplier, which provides the lower portion of the decimal final product of the multiplier significant digit width left-justified in the multipler 1 and the higher portion of the decimal final product as an output from the decimal loop adder 7 at a final operation cycle. Thereafter the higher portion of the decimal final product, which is provided as an output from the decimal loop adder 7, is transferred to and set in the multiplicand register 2 through line 98.
In the manner mentioned above, the product represented in binary coded decimal form can be obtained by multiplying the multiplicand represented in binary coded decimal form by the multiplier represented in the same notation. The speed up of the operation of the decimal loop adder 7 provides one means of realizing high speed decimal multiplication.
The decimal loop adder is commonly constructed as shown in FIG. 3. The operation thereof is as follows. Prior to an addition of two inputs A and B, first, the input A is added with 6 for each digit of the binary coded decimal thereof by 6- adder circuits 9.sub.i, 9.sub.i+1, . . . (i: any digit) (providing A'), and this output A' and the other input B are added in binary operation (providing R). During the binary addition, when a carry does not occur from one digit of the binary coded decimal (named as a first case), R is 6-subtracted for each digit of the binary coded decimal by 6-subtraction circuits 11.sub.i, 11.sub.i+1. When the carry occurs (named as a second case), a 6-subtraction correction circuits 12.sub.i, 12.sub.i+1 are controlled so that the value of R itself is used as an output from the decimal loop adder. FIG. 4a shows an example of the first case and FIG. 4b shows an example of the second case. Such a technique is also disclosed in H. HELLERMAN "DIGITAL COMPUTER SYSTEM PRINCIPLES" (McGRAW-HILL BOOK Co., 1967), pp. 300-301. In the manner described above, two binary coded decimals are input and binary-added and the sum thereof is obtained. But, since in the binary addition, a next operation cycle cannot be started till the carry is transferred from a least significant bit to a most significant bit, this technique has a limit of implementing high-speed operation from the point of view of the system.
On the other hand, one exemplary construction realizing the high speed operation of a loop adder in a binary multiplication apparatus is shown in FIG. 5. Such a construction is disclosed in K. HWANG "Computer Arithmetic PRINCIPLES, ARCHITECTURE, AND DESIGN" (John Wiley & Sons, Inc., 1979), etc. The carry occurring during the multiplication is saved or reserved as a saved carry in the loop adder, and after all of the significant digits of a multiplier are subjected to, the operation of the carry propagation is lastly processed. In FIG. 5, the multiplication of a multiplier set in the register 1 and a multiplicand set in the multiplicand register 2 is performed as follows. When a binary partial product generator 13 is activated, a first binary partial product operation of the multiplicand set in the multiplicand register 2 and the predetermined processing width partitioned-out from the lower order bit of the multiplier set in the multiplier register 1 is performed, and this first partial product is set in partial product registers 16 and 17. A carry save adder is commonly used also as the binary partial product generator 13. And in FIG. 5, the partial product is also in the partial product sum register 16 and the partial product carry register 17 in the forms of a sum (partial sum) and saved carry, respectively. At the same time, zero (0) is set in an intermediate sum register 14 and an intermediate product carry register 15 as an initial value, and the multiplier set in the multiplier register 1 is right-shifted by the shifter 13 after a necessary width of data is partitioned out, and set in the multiplier register 1. The initial value zero set in the intermediate product sum register 14 and the intermediate product carry register 15, and the first partial product sum and carry set in the partial product sum register 16 and the partial product carry register, respectively, are carry-save-added by two stages of carry save adders 18 and 21 both encircled by a dashed line 23, and the sum and carry of the first intermediate product are transferred to and set in the intermediate product sum register 14 and the intermediate product carry register 15. Then, where the carry output from the carry save adder is transferred, to a next stage of the adder, it is one-bit left-shifted for the purpose of carry alignment by one-bit-left-shift circuits 19, 20 and 22. The sum output from the carry save adder 21 and the output from the one-bit-left-shift circuit 22 are right-shifted by shifters 24 and 25 by the predetermined processing data width of the multiplier, and set in the intermediate product sum register 14 and the intermediate product carry register 15. The data of the lowest order multiplier predetermined processing width of the sum output from the carry save adder and the output from the one-bit-left-shift circuit 22, both being equal to predetermined processing width of the multiplier, are input to a spill adder 26 and binary-added therein. This output from the spill adder 26, i.e., the lowest order of the final product with the predetermined processing multiplier width the final product, is transferred to and set in the highest order position of predetermined processing multiplier width of the multiplier register 1.
The similar processing is repeated for all of the significant digits of the multiplier. Thus, the lower order portion of the final product with multiplier significant digits width is left-justified in the multiplier register 1, while the higher order portion of the final product is obtained from the sum output of the carry save adder 21 and the output from the one bit left shift circuit 22, which is obtained by one-bit left-shifting the carry output of the carry save adder 21, in the forms of sum and carry, respectively, at a final operation cycle. The sum and carry of the higher order portion of the final product are input to a full adder 27 and binary-added therein. The output from the full adder 27, i.e., the higher order portion of the final product is transferred to and set in the multiplicand register 2.
In the manner mentioned above, a binary product is obtained by multiplying a binary multiplicand by a binary multiplier. In this case, as seen from FIG. 5, the carry save adders 18 and 21 can be constructed with one or two stages of gates, and the waiting for the completion of the carry propagation from the least significant bit of the adder to the most significant bit thereof is not required, so that a high-speed loop adder can be constructed. However, unlike a binary code, a binary coded decimal uses four bits width to represent one digit, and deals with 0 to 9 only as a numerical value so that a carry save adder for binary number at the sum output and carry output of which binary values (1010).sub.2 -(1111).sub.2 exceeding a decimal notation representation appear can be disadvantageously unapplicable to a decimal multiplication as it is.